/ Celestin Apprentice 4 / Apprentice-Release4.iso / Source Code / Add-Ons / MPW / MPW noweb 2.7 / examples / primes.nw

< prev

next >

MacOS 8.1

Win98

DOS

browse contents

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 25 20 43 6f 70 79 72 69 | 67 68 74 20 31 39 39 31 |% Copyri|ght 1991|
|00000010| 20 62 79 20 4e 6f 72 6d | 61 6e 20 52 61 6d 73 65 | by Norm|an Ramse|
|00000020| 79 2e 20 20 41 6c 6c 20 | 72 69 67 68 74 73 20 72 |y.  All |rights r|
|00000030| 65 73 65 72 76 65 64 2e | 0d 25 20 53 65 65 20 66 |eserved.|.% See f|
|00000040| 69 6c 65 20 43 4f 50 59 | 52 49 47 48 54 20 66 6f |ile COPY|RIGHT fo|
|00000050| 72 20 6d 6f 72 65 20 69 | 6e 66 6f 72 6d 61 74 69 |r more i|nformati|
|00000060| 6f 6e 2e 0d 0d 25 20 6c | 32 68 20 73 75 62 73 74 |on...% l|2h subst|
|00000070| 69 74 75 74 69 6f 6e 20 | 6e 77 20 3c 74 74 3e 6e |itution |nw <tt>n|
|00000080| 6f 77 65 62 3c 2f 74 74 | 3e 0d 25 20 73 6f 6d 65 |oweb</tt|>.% some|
|00000090| 20 69 6e 73 61 6e 69 74 | 79 20 69 73 20 6e 65 65 | insanit|y is nee|
|000000a0| 64 65 64 20 74 6f 20 61 | 76 6f 69 64 20 67 65 74 |ded to a|void get|
|000000b0| 74 69 6e 67 20 61 20 64 | 6f 75 62 6c 65 20 73 71 |ting a d|ouble sq|
|000000c0| 75 61 72 65 20 62 72 61 | 63 6b 65 74 0d 25 20 6c |uare bra|cket.% l|
|000000d0| 32 68 20 73 75 62 73 74 | 69 74 75 74 69 6f 6e 20 |2h subst|itution |
|000000e0| 5b 20 3c 62 3e 5b 3c 2f | 62 3e 3c 62 3e 5b 3c 2f |[ <b>[</|b><b>[</|
|000000f0| 62 3e 20 0d 25 20 6c 32 | 68 20 73 75 62 73 74 69 |b> .% l2|h substi|
|00000100| 74 75 74 69 6f 6e 20 5d | 20 3c 62 3e 5d 3c 2f 62 |tution ]| <b>]</b|
|00000110| 3e 3c 62 3e 5d 3c 2f 62 | 3e 0d 5c 64 65 66 5c 6e |><b>]</b|>.\def\n|
|00000120| 77 7b 7b 5c 74 74 20 6e | 6f 77 65 62 7d 7d 0d 5c |w{{\tt n|oweb}}.\|
|00000130| 64 65 66 5c 5b 7b 5c 69 | 66 68 6d 6f 64 65 5c 20 |def\[{\i|fhmode\ |
|00000140| 5c 66 69 24 5b 5c 6d 6b | 65 72 6e 2d 32 6d 75 5b |\fi$[\mk|ern-2mu[|
|00000150| 24 7d 0d 5c 64 65 66 5c | 5d 7b 24 5d 5c 6d 6b 65 |$}.\def\|]{$]\mke|
|00000160| 72 6e 2d 32 6d 75 5d 24 | 7d 0d 0d 5c 74 69 74 6c |rn-2mu]$|}..\titl|
|00000170| 65 7b 50 72 69 6e 74 69 | 6e 67 20 50 72 69 6d 65 |e{Printi|ng Prime|
|00000180| 73 3a 20 41 6e 20 65 78 | 61 6d 70 6c 65 20 6f 66 |s: An ex|ample of|
|00000190| 20 5c 6e 77 7d 0d 0d 5c | 73 65 63 74 69 6f 6e 7b | \nw}..\|section{|
|000001a0| 50 72 69 6e 74 69 6e 67 | 20 50 72 69 6d 65 73 3a |Printing| Primes:|
|000001b0| 20 41 6e 20 65 78 61 6d | 70 6c 65 20 6f 66 20 5c | An exam|ple of \|
|000001c0| 6e 77 7d 0d 54 68 65 20 | 66 6f 6c 6c 6f 77 69 6e |nw}.The |followin|
|000001d0| 67 20 70 72 6f 67 72 61 | 6d 20 69 73 20 65 73 73 |g progra|m is ess|
|000001e0| 65 6e 74 69 61 6c 6c 79 | 20 74 68 65 20 70 72 6f |entially| the pro|
|000001f0| 67 72 61 6d 20 74 68 61 | 74 20 61 70 70 65 61 72 |gram tha|t appear|
|00000200| 73 20 69 6e 20 0d 52 65 | 66 65 72 65 6e 63 65 7e |s in .Re|ference~|
|00000210| 5c 63 69 74 65 7b 6b 6e | 75 74 68 3a 6c 69 74 65 |\cite{kn|uth:lite|
|00000220| 72 61 74 65 7d 2c 20 74 | 68 65 20 66 69 72 73 74 |rate}, t|he first|
|00000230| 20 61 72 74 69 63 6c 65 | 20 6f 6e 20 6c 69 74 65 | article| on lite|
|00000240| 72 61 74 65 20 70 72 6f | 67 72 61 6d 6d 69 6e 67 |rate pro|gramming|
|00000250| 2c 0d 62 75 74 20 72 65 | 6e 64 65 72 65 64 20 75 |,.but re|ndered u|
|00000260| 73 69 6e 67 20 5c 6e 77 | 2e 0d 41 6e 20 69 6d 70 |sing \nw|..An imp|
|00000270| 6f 72 74 61 6e 74 20 64 | 69 66 66 65 72 65 6e 74 |ortant d|ifferent|
|00000280| 73 20 69 73 20 74 68 65 | 20 7b 5c 74 74 20 57 45 |s is the| {\tt WE|
|00000290| 42 7d 20 68 61 73 20 6d | 61 63 72 6f 73 2c 20 62 |B} has m|acros, b|
|000002a0| 75 74 20 5c 6e 77 5c 20 | 64 6f 65 73 20 6e 6f 74 |ut \nw\ |does not|
|000002b0| 2e 0d 4b 6e 75 74 68 27 | 73 20 70 72 6f 67 72 61 |..Knuth'|s progra|
|000002c0| 6d 20 69 73 20 69 74 73 | 65 6c 66 20 65 73 73 65 |m is its|elf esse|
|000002d0| 6e 74 69 61 6c 6c 79 20 | 74 68 65 20 73 61 6d 65 |ntially |the same|
|000002e0| 20 61 73 20 45 64 73 67 | 65 72 20 44 69 6a 6b 73 | as Edsg|er Dijks|
|000002f0| 74 72 61 27 73 20 0d 60 | 60 66 69 72 73 74 20 65 |tra's .`|`first e|
|00000300| 78 61 6d 70 6c 65 20 6f | 66 20 73 74 65 70 2d 77 |xample o|f step-w|
|00000310| 69 73 65 20 70 72 6f 67 | 72 61 6d 20 63 6f 6d 70 |ise prog|ram comp|
|00000320| 6f 73 69 74 69 6f 6e 2e | 27 27 7e 5c 63 69 74 65 |osition.|''~\cite|
|00000330| 5b 70 61 67 65 73 0d 32 | 36 2d 2d 33 39 5d 7b 64 |[pages.2|6--39]{d|
|00000340| 61 68 6c 3a 73 74 72 75 | 63 74 75 72 65 64 7d 2e |ahl:stru|ctured}.|
|00000350| 20 20 0d 0d 44 69 6a 6b | 73 74 72 61 27 73 20 70 |  ..Dijk|stra's p|
|00000360| 72 6f 67 72 61 6d 20 70 | 72 69 6e 74 73 20 61 20 |rogram p|rints a |
|00000370| 74 61 62 6c 65 20 6f 66 | 20 74 68 65 20 66 69 72 |table of| the fir|
|00000380| 73 74 20 74 68 6f 75 73 | 61 6e 64 20 70 72 69 6d |st thous|and prim|
|00000390| 65 20 6e 75 6d 62 65 72 | 73 2e 0d 57 65 20 73 68 |e number|s..We sh|
|000003a0| 61 6c 6c 20 62 65 67 69 | 6e 20 61 73 20 68 65 20 |all begi|n as he |
|000003b0| 64 69 64 2c 20 62 79 20 | 72 65 64 75 63 69 6e 67 |did, by |reducing|
|000003c0| 20 74 68 65 20 65 6e 74 | 69 72 65 20 70 72 6f 67 | the ent|ire prog|
|000003d0| 72 61 6d 20 74 6f 20 69 | 74 73 0d 74 6f 70 2d 6c |ram to i|ts.top-l|
|000003e0| 65 76 65 6c 20 64 65 73 | 63 72 69 70 74 69 6f 6e |evel des|cription|
|000003f0| 2e 0d 0d 3c 3c 2a 3e 3e | 3d 0d 3c 3c 70 72 6f 67 |...<<*>>|=.<<prog|
|00000400| 72 61 6d 20 74 6f 20 70 | 72 69 6e 74 20 74 68 65 |ram to p|rint the|
|00000410| 20 66 69 72 73 74 20 74 | 68 6f 75 73 61 6e 64 20 | first t|housand |
|00000420| 70 72 69 6d 65 20 6e 75 | 6d 62 65 72 73 3e 3e 0d |prime nu|mbers>>.|
|00000430| 40 0d 5c 5b 44 6f 75 62 | 6c 65 20 62 72 61 63 6b |@.\[Doub|le brack|
|00000440| 65 74 73 20 77 69 6c 6c | 20 62 65 20 75 73 65 64 |ets will| be used|
|00000450| 20 69 6e 20 77 68 61 74 | 20 66 6f 6c 6c 6f 77 73 | in what| follows|
|00000460| 20 74 6f 20 65 6e 63 6c | 6f 73 65 20 63 6f 6d 6d | to encl|ose comm|
|00000470| 65 6e 74 73 0d 72 65 6c | 61 74 69 6e 67 20 74 6f |ents.rel|ating to|
|00000480| 20 5c 6e 77 5c 20 69 74 | 73 65 6c 66 2e 20 20 0d | \nw\ it|self.  .|
|00000490| 54 68 69 73 20 64 65 66 | 69 6e 69 74 69 6f 6e 20 |This def|inition |
|000004a0| 6f 66 20 74 68 65 20 72 | 6f 6f 74 20 6d 6f 64 75 |of the r|oot modu|
|000004b0| 6c 65 20 63 6f 75 6c 64 | 20 68 61 76 65 20 62 65 |le could| have be|
|000004c0| 65 6e 20 65 6c 69 6d 69 | 6e 61 74 65 64 20 62 79 |en elimi|nated by|
|000004d0| 0d 63 68 6f 6f 73 69 6e | 67 20 74 6f 20 75 73 65 |.choosin|g to use|
|000004e0| 20 0d 5c 62 65 67 69 6e | 7b 71 75 6f 74 65 7d 0d | .\begin|{quote}.|
|000004f0| 5c 74 74 20 6e 6f 74 61 | 6e 67 6c 65 20 2d 52 27 |\tt nota|ngle -R'|
|00000500| 70 72 6f 67 72 61 6d 20 | 74 6f 20 70 72 69 6e 74 |program |to print|
|00000510| 20 74 68 65 20 66 69 72 | 73 74 20 74 68 6f 75 73 | the fir|st thous|
|00000520| 61 6e 64 20 70 72 69 6d | 65 20 6e 75 6d 62 65 72 |and prim|e number|
|00000530| 73 27 0d 5c 65 6e 64 7b | 71 75 6f 74 65 7d 0d 74 |s'.\end{|quote}.t|
|00000540| 6f 20 65 78 74 72 61 63 | 74 20 74 68 65 20 70 72 |o extrac|t the pr|
|00000550| 6f 67 72 61 6d 2e 5c 5d | 0d 40 20 54 68 69 73 20 |ogram.\]|.@ This |
|00000560| 70 72 6f 67 72 61 6d 20 | 68 61 73 20 6e 6f 20 69 |program |has no i|
|00000570| 6e 70 75 74 2c 20 62 65 | 63 61 75 73 65 20 77 65 |nput, be|cause we|
|00000580| 20 77 61 6e 74 20 74 6f | 20 6b 65 65 70 20 69 74 | want to| keep it|
|00000590| 20 73 69 6d 70 6c 65 2e | 0d 54 68 65 20 72 65 73 | simple.|.The res|
|000005a0| 75 6c 74 20 6f 66 20 74 | 68 65 20 70 72 6f 67 72 |ult of t|he progr|
|000005b0| 61 6d 20 77 69 6c 6c 20 | 62 65 20 74 6f 20 70 72 |am will |be to pr|
|000005c0| 6f 64 75 63 65 20 61 20 | 6c 69 73 74 20 6f 66 20 |oduce a |list of |
|000005d0| 74 68 65 20 66 69 72 73 | 74 0d 74 68 6f 75 73 61 |the firs|t.thousa|
|000005e0| 6e 64 20 70 72 69 6d 65 | 20 6e 75 6d 62 65 72 73 |nd prime| numbers|
|000005f0| 2c 20 61 6e 64 20 74 68 | 69 73 20 6c 69 73 74 20 |, and th|is list |
|00000600| 77 69 6c 6c 20 61 70 70 | 65 61 72 20 6f 6e 20 74 |will app|ear on t|
|00000610| 68 65 20 5b 5b 6f 75 74 | 70 75 74 5d 5d 0d 66 69 |he [[out|put]].fi|
|00000620| 6c 65 2e 0d 0d 53 69 6e | 63 65 20 74 68 65 72 65 |le...Sin|ce there|
|00000630| 20 69 73 20 6e 6f 20 69 | 6e 70 75 74 2c 20 77 65 | is no i|nput, we|
|00000640| 20 64 65 63 6c 61 72 65 | 20 74 68 65 20 76 61 6c | declare| the val|
|00000650| 75 65 20 5b 5b 6d 20 3d | 20 31 30 30 30 5d 5d 20 |ue [[m =| 1000]] |
|00000660| 61 73 20 61 0d 63 6f 6d | 70 69 6c 65 2d 74 69 6d |as a.com|pile-tim|
|00000670| 65 20 63 6f 6e 73 74 61 | 6e 74 2e 0d 54 68 65 20 |e consta|nt..The |
|00000680| 70 72 6f 67 72 61 6d 20 | 69 74 73 65 6c 66 20 69 |program |itself i|
|00000690| 73 20 63 61 70 61 62 6c | 65 20 6f 66 20 67 65 6e |s capabl|e of gen|
|000006a0| 65 72 61 74 69 6e 67 20 | 74 68 65 20 66 69 72 73 |erating |the firs|
|000006b0| 74 20 5b 5b 6d 5d 5d 20 | 70 72 69 6d 65 0d 6e 75 |t [[m]] |prime.nu|
|000006c0| 6d 62 65 72 73 20 66 6f | 72 20 61 6e 79 20 70 6f |mbers fo|r any po|
|000006d0| 73 69 74 69 76 65 20 5b | 5b 6d 5d 5d 2c 20 61 73 |sitive [|[m]], as|
|000006e0| 20 6c 6f 6e 67 20 61 73 | 20 74 68 65 20 63 6f 6d | long as| the com|
|000006f0| 70 75 74 65 72 27 73 20 | 66 69 6e 69 74 65 0d 6c |puter's |finite.l|
|00000700| 69 6d 69 74 61 74 69 6f | 6e 73 20 61 72 65 20 6e |imitatio|ns are n|
|00000710| 6f 74 20 65 78 63 65 65 | 64 65 64 2e 0d 3c 3c 70 |ot excee|ded..<<p|
|00000720| 72 6f 67 72 61 6d 20 74 | 6f 20 70 72 69 6e 74 20 |rogram t|o print |
|00000730| 74 68 65 20 66 69 72 73 | 74 20 74 68 6f 75 73 61 |the firs|t thousa|
|00000740| 6e 64 20 70 72 69 6d 65 | 20 6e 75 6d 62 65 72 73 |nd prime| numbers|
|00000750| 3e 3e 3d 0d 70 72 6f 67 | 72 61 6d 20 70 72 69 6e |>>=.prog|ram prin|
|00000760| 74 5f 70 72 69 6d 65 73 | 28 6f 75 74 70 75 74 29 |t_primes|(output)|
|00000770| 3b 0d 20 20 63 6f 6e 73 | 74 20 6d 20 3d 20 31 30 |;.  cons|t m = 10|
|00000780| 30 30 3b 0d 20 20 20 20 | 20 20 20 20 3c 3c 6f 74 |00;.    |    <<ot|
|00000790| 68 65 72 20 63 6f 6e 73 | 74 61 6e 74 73 20 6f 66 |her cons|tants of|
|000007a0| 20 74 68 65 20 70 72 6f | 67 72 61 6d 3e 3e 0d 20 | the pro|gram>>. |
|000007b0| 20 76 61 72 20 3c 3c 76 | 61 72 69 61 62 6c 65 73 | var <<v|ariables|
|000007c0| 20 6f 66 20 74 68 65 20 | 70 72 6f 67 72 61 6d 3e | of the |program>|
|000007d0| 3e 0d 20 20 20 20 62 65 | 67 69 6e 20 3c 3c 70 72 |>.    be|gin <<pr|
|000007e0| 69 6e 74 20 74 68 65 20 | 66 69 72 73 74 20 5b 5b |int the |first [[|
|000007f0| 6d 5d 5d 20 70 72 69 6d | 65 20 6e 75 6d 62 65 72 |m]] prim|e number|
|00000800| 73 3e 3e 0d 20 20 20 20 | 65 6e 64 2e 0d 40 20 25 |s>>.    |end..@ %|
|00000810| 64 65 66 20 70 72 69 6e | 74 5f 70 72 69 6d 65 73 |def prin|t_primes|
|00000820| 0d 0d 5c 73 65 63 74 69 | 6f 6e 7b 50 6c 61 6e 20 |..\secti|on{Plan |
|00000830| 6f 66 20 74 68 65 20 70 | 72 6f 67 72 61 6d 7d 0d |of the p|rogram}.|
|00000840| 57 65 20 73 68 61 6c 6c | 20 70 72 6f 63 65 65 64 |We shall| proceed|
|00000850| 20 74 6f 20 66 69 6c 6c | 20 6f 75 74 20 74 68 65 | to fill| out the|
|00000860| 20 72 65 73 74 20 6f 66 | 20 74 68 65 20 70 72 6f | rest of| the pro|
|00000870| 67 72 61 6d 20 62 79 20 | 6d 61 6b 69 6e 67 0d 77 |gram by |making.w|
|00000880| 68 61 74 65 76 65 72 20 | 64 65 63 69 73 69 6f 6e |hatever |decision|
|00000890| 73 20 73 65 65 6d 20 65 | 61 73 69 65 73 74 20 61 |s seem e|asiest a|
|000008a0| 74 20 65 61 63 68 20 73 | 74 65 70 3b 20 74 68 65 |t each s|tep; the|
|000008b0| 20 69 64 65 61 20 77 69 | 6c 6c 20 62 65 20 74 6f | idea wi|ll be to|
|000008c0| 0d 73 74 72 69 76 65 20 | 66 6f 72 20 73 69 6d 70 |.strive |for simp|
|000008d0| 6c 69 63 69 74 79 20 66 | 69 72 73 74 20 61 6e 64 |licity f|irst and|
|000008e0| 20 65 66 66 69 63 69 65 | 6e 63 79 20 6c 61 74 65 | efficie|ncy late|
|000008f0| 72 2c 20 69 6e 20 6f 72 | 64 65 72 20 74 6f 20 73 |r, in or|der to s|
|00000900| 65 65 0d 77 68 65 72 65 | 20 74 68 69 73 20 6c 65 |ee.where| this le|
|00000910| 61 64 73 20 75 73 2e 0d | 54 68 65 20 66 69 6e 61 |ads us..|The fina|
|00000920| 6c 20 70 72 6f 67 72 61 | 6d 20 6d 61 79 20 6e 6f |l progra|m may no|
|00000930| 74 20 62 65 20 6f 70 74 | 69 6d 75 6d 2c 20 62 75 |t be opt|imum, bu|
|00000940| 74 20 77 65 20 77 61 6e | 74 20 69 74 20 74 6f 20 |t we wan|t it to |
|00000950| 62 65 20 72 65 6c 69 61 | 62 6c 65 2c 0d 77 65 6c |be relia|ble,.wel|
|00000960| 6c 20 6d 6f 74 69 76 61 | 74 65 64 2c 20 61 6e 64 |l motiva|ted, and|
|00000970| 20 72 65 61 73 6f 6e 61 | 62 6c 79 20 66 61 73 74 | reasona|bly fast|
|00000980| 2e 0d 0d 4c 65 74 20 75 | 73 20 64 65 63 69 64 65 |...Let u|s decide|
|00000990| 20 61 74 20 74 68 69 73 | 20 70 6f 69 6e 74 20 74 | at this| point t|
|000009a0| 6f 20 6d 61 69 6e 74 61 | 69 6e 20 61 20 74 61 62 |o mainta|in a tab|
|000009b0| 6c 65 20 74 68 61 74 20 | 69 6e 63 6c 75 64 65 73 |le that |includes|
|000009c0| 20 61 6c 6c 20 6f 66 0d | 74 68 65 20 70 72 69 6d | all of.|the prim|
|000009d0| 65 20 6e 75 6d 65 62 72 | 73 20 74 68 61 74 20 77 |e numebr|s that w|
|000009e0| 69 6c 6c 20 62 65 20 67 | 65 6e 65 72 61 74 65 64 |ill be g|enerated|
|000009f0| 2c 20 61 6e 64 20 74 6f | 20 73 65 70 61 65 72 61 |, and to| sepaera|
|00000a00| 74 65 20 74 68 65 0d 67 | 65 6e 72 65 61 74 69 6f |te the.g|enreatio|
|00000a10| 6e 20 70 72 6f 62 6c 65 | 6d 20 66 72 6f 6d 20 74 |n proble|m from t|
|00000a20| 68 65 20 70 72 69 6e 74 | 69 6e 67 20 70 72 6f 62 |he print|ing prob|
|00000a30| 6c 65 6d 2e 0d 3c 3c 70 | 72 69 6e 74 20 74 68 65 |lem..<<p|rint the|
|00000a40| 20 66 69 72 73 74 20 5b | 5b 6d 5d 5d 20 70 72 69 | first [|[m]] pri|
|00000a50| 6d 65 20 6e 75 6d 62 65 | 72 73 3e 3e 3d 0d 3c 3c |me numbe|rs>>=.<<|
|00000a60| 66 69 6c 6c 20 74 61 62 | 6c 65 20 5b 5b 70 5d 5d |fill tab|le [[p]]|
|00000a70| 20 77 69 74 68 20 74 68 | 65 20 66 69 72 73 74 20 | with th|e first |
|00000a80| 5b 5b 6d 5d 5d 20 70 72 | 69 6d 65 20 6e 75 6d 62 |[[m]] pr|ime numb|
|00000a90| 65 72 73 3e 3e 3b 0d 3c | 3c 70 72 69 6e 74 20 74 |ers>>;.<|<print t|
|00000aa0| 61 62 6c 65 20 5b 5b 70 | 5d 5d 3e 3e 0d 40 0d 48 |able [[p|]]>>.@.H|
|00000ab0| 6f 77 20 73 68 6f 75 6c | 64 20 74 61 62 6c 65 20 |ow shoul|d table |
|00000ac0| 5b 5b 70 5d 5d 20 62 65 | 20 72 65 70 72 65 73 65 |[[p]] be| represe|
|00000ad0| 6e 74 65 64 3f 0d 54 77 | 6f 20 70 6f 73 73 69 62 |nted?.Tw|o possib|
|00000ae0| 69 6c 69 74 69 65 73 20 | 73 75 67 67 65 73 74 20 |ilities |suggest |
|00000af0| 74 68 65 6d 73 65 6c 76 | 65 73 3a 20 57 65 20 63 |themselv|es: We c|
|00000b00| 6f 75 6c 64 20 63 6f 6e | 73 74 72 75 63 74 20 61 |ould con|struct a|
|00000b10| 0d 73 69 66 66 69 63 69 | 65 6e 74 6c 79 20 6c 61 |.siffici|ently la|
|00000b20| 72 67 65 20 61 72 61 79 | 20 6f 66 20 62 6f 6f 6c |rge aray| of bool|
|00000b30| 65 61 6e 20 76 61 6c 75 | 65 73 20 69 6e 20 77 68 |ean valu|es in wh|
|00000b40| 69 74 68 20 74 68 65 20 | 24 6b 24 74 68 20 65 6e |ith the |$k$th en|
|00000b50| 74 72 79 20 69 73 0d 5b | 5b 74 72 75 65 5d 5d 20 |try is.[|[true]] |
|00000b60| 69 66 20 61 6e 64 20 6f | 6e 6c 79 20 69 66 20 74 |if and o|nly if t|
|00000b70| 68 65 20 6e 75 6d 62 65 | 72 20 24 6b 24 20 69 73 |he numbe|r $k$ is|
|00000b80| 20 70 72 69 6d 65 3b 20 | 6f 72 20 77 65 20 63 6f | prime; |or we co|
|00000b90| 75 6c 64 20 62 75 69 6c | 64 20 61 6e 0d 61 72 72 |uld buil|d an.arr|
|00000ba0| 61 79 20 6f 66 20 69 6e | 74 65 67 65 72 73 20 69 |ay of in|tegers i|
|00000bb0| 6e 20 77 68 69 63 68 20 | 74 68 65 20 24 6b 24 74 |n which |the $k$t|
|00000bc0| 68 20 65 6e 74 72 79 20 | 69 73 20 74 68 65 20 24 |h entry |is the $|
|00000bd0| 6b 24 74 68 20 70 72 69 | 6d 65 20 6e 75 6d 62 65 |k$th pri|me numbe|
|00000be0| 72 2e 0d 4c 65 74 20 75 | 73 20 63 68 6f 6f 73 65 |r..Let u|s choose|
|00000bf0| 20 74 68 65 20 6c 61 74 | 74 65 72 20 61 6c 74 65 | the lat|ter alte|
|00000c00| 72 6e 61 74 69 63 65 2c | 20 62 79 20 69 6e 74 72 |rnatice,| by intr|
|00000c10| 6f 64 75 63 69 6e 67 20 | 61 6e 20 69 6e 74 65 72 |oducing |an inter|
|00000c20| 65 67 65 72 0d 61 72 72 | 61 79 20 63 61 6c 6c 65 |eger.arr|ay calle|
|00000c30| 64 20 5b 5b 70 5b 31 2e | 2e 6d 5d 5d 5d 2e 0d 49 |d [[p[1.|.m]]]..I|
|00000c40| 6e 20 74 68 65 20 64 6f | 63 75 6d 65 6e 74 61 74 |n the do|cumentat|
|00000c50| 69 6f 6e 20 62 65 63 6c | 6f 65 77 2c 20 74 68 65 |ion becl|oew, the|
|00000c60| 20 6e 6f 74 61 74 69 6f | 6e 20 5b 5b 70 5b 6b 5d | notatio|n [[p[k]|
|00000c70| 5d 5d 20 77 69 6c 6c 20 | 72 65 66 65 72 20 74 6f |]] will |refer to|
|00000c80| 20 74 68 65 0d 5b 5b 6b | 5d 5d 74 68 20 65 6c 65 | the.[[k|]]th ele|
|00000c90| 6d 65 6e 74 20 6f 66 20 | 74 68 65 20 61 72 72 61 |ment of |the arra|
|00000ca0| 79 20 5b 5b 70 5d 5d 2c | 20 77 68 69 6c 65 20 24 |y [[p]],| while $|
|00000cb0| 70 5f 6b 24 20 77 69 6c | 6c 20 72 65 66 65 72 20 |p_k$ wil|l refer |
|00000cc0| 74 6f 20 74 68 65 0d 24 | 6b 24 74 68 20 70 72 69 |to the.$|k$th pri|
|00000cd0| 6d 65 20 6e 75 6d 62 65 | 72 2e 0d 49 66 20 74 68 |me numbe|r..If th|
|00000ce0| 65 20 70 72 6f 67 72 61 | 6d 20 69 73 20 63 6f 72 |e progra|m is cor|
|00000cf0| 72 65 63 74 20 5b 5b 70 | 5b 6b 5d 5d 5d 20 77 69 |rect [[p|[k]]] wi|
|00000d00| 6c 6c 20 65 71 75 61 6c | 20 24 70 5f 6b 24 20 6f |ll equal| $p_k$ o|
|00000d10| 72 20 69 74 20 77 69 6c | 6c 20 6e 6f 74 20 79 65 |r it wil|l not ye|
|00000d20| 74 0d 68 61 76 65 20 6e | 62 65 65 6e 20 61 73 69 |t.have n|been asi|
|00000d30| 67 6e 65 64 20 61 6e 79 | 20 76 61 6c 75 65 2e 0d |gned any| value..|
|00000d40| 3c 3c 76 61 72 69 61 62 | 6c 65 73 20 6f 66 20 74 |<<variab|les of t|
|00000d50| 68 65 20 70 72 6f 67 72 | 61 6d 3e 3e 3d 0d 70 3a |he progr|am>>=.p:|
|00000d60| 20 61 72 72 61 79 20 5b | 31 2e 2e 6d 5d 20 6f 66 | array [|1..m] of|
|00000d70| 20 69 6e 74 65 67 65 72 | 3b 20 0d 20 20 20 20 20 | integer|; .     |
|00000d80| 20 7b 20 74 68 65 20 66 | 69 72 73 74 20 6d 20 70 | { the f|irst m p|
|00000d90| 72 69 6d 65 20 6e 75 6d | 62 65 72 73 2c 20 69 6e |rime num|bers, in|
|00000da0| 20 69 6e 63 72 65 61 73 | 69 6e 67 20 6f 72 64 65 | increas|ing orde|
|00000db0| 72 20 7d 0d 40 0d 5c 73 | 65 63 74 69 6f 6e 7b 54 |r }.@.\s|ection{T|
|00000dc0| 68 65 20 6f 75 74 70 75 | 74 20 70 68 61 73 65 7d |he outpu|t phase}|
|00000dd0| 0d 3c 3c 6f 74 68 65 72 | 20 63 6f 6e 73 74 61 6e |.<<other| constan|
|00000de0| 74 73 20 6f 66 20 74 68 | 65 20 70 72 6f 67 72 61 |ts of th|e progra|
|00000df0| 6d 3e 3e 3d 0d 72 72 20 | 3d 20 35 30 3b 0d 63 63 |m>>=.rr |= 50;.cc|
|00000e00| 20 3d 20 34 3b 0d 77 77 | 20 3d 20 31 30 3b 0d 3c | = 4;.ww| = 10;.<|
|00000e10| 3c 76 61 72 69 61 62 6c | 65 73 20 6f 66 20 74 68 |<variabl|es of th|
|00000e20| 65 20 70 72 6f 67 72 61 | 6d 3e 3e 3d 0d 70 61 67 |e progra|m>>=.pag|
|00000e30| 65 5f 6e 75 6d 62 65 72 | 3a 20 69 6e 74 65 67 65 |e_number|: intege|
|00000e40| 72 3b 0d 70 61 67 65 5f | 6f 66 66 73 65 74 3a 20 |r;.page_|offset: |
|00000e50| 69 6e 74 65 67 65 72 3b | 0d 72 6f 77 5f 6f 66 66 |integer;|.row_off|
|00000e60| 73 65 74 3a 20 69 6e 74 | 65 67 65 72 3b 0d 63 3a |set: int|eger;.c:|
|00000e70| 20 30 2e 2e 63 63 3b 0d | 40 20 25 64 65 66 20 70 | 0..cc;.|@ %def p|
|00000e80| 61 67 65 5f 6e 75 6d 62 | 65 72 20 70 61 67 65 5f |age_numb|er page_|
|00000e90| 6f 66 66 73 65 74 20 72 | 6f 77 5f 6f 66 66 73 65 |offset r|ow_offse|
|00000ea0| 74 0d 3c 3c 70 72 69 6e | 74 20 74 61 62 6c 65 20 |t.<<prin|t table |
|00000eb0| 5b 5b 70 5d 5d 3e 3e 3d | 0d 62 65 67 69 6e 20 70 |[[p]]>>=|.begin p|
|00000ec0| 61 67 65 5f 6e 75 6d 62 | 65 72 20 3a 3d 20 31 3b |age_numb|er := 1;|
|00000ed0| 20 70 61 67 65 5f 6f 66 | 66 73 65 74 20 3a 3d 20 | page_of|fset := |
|00000ee0| 31 3b 0d 77 68 69 6c 65 | 20 70 61 67 65 5f 6f 66 |1;.while| page_of|
|00000ef0| 66 73 65 74 20 3c 3d 20 | 6d 20 64 6f 0d 20 20 62 |fset <= |m do.  b|
|00000f00| 65 67 69 6e 20 3c 3c 6f | 75 74 70 75 74 20 61 20 |egin <<o|utput a |
|00000f10| 70 61 67 65 20 6f 66 20 | 61 6e 73 77 65 72 73 3e |page of |answers>|
|00000f20| 3e 3b 0d 20 20 70 61 67 | 65 5f 6e 75 6d 62 65 72 |>;.  pag|e_number|
|00000f30| 20 3a 3d 20 70 61 67 65 | 5f 6e 75 6d 62 65 72 20 | := page|_number |
|00000f40| 2b 20 31 3b 0d 20 20 70 | 61 67 65 5f 6f 66 66 73 |+ 1;.  p|age_offs|
|00000f50| 65 74 20 3a 3d 20 70 61 | 67 65 5f 70 6f 66 66 73 |et := pa|ge_poffs|
|00000f60| 65 74 20 2b 20 72 72 20 | 2a 20 63 63 3b 0d 20 20 |et + rr |* cc;.  |
|00000f70| 65 6e 64 3b 0d 65 6e 64 | 0d 3c 3c 6f 75 74 70 75 |end;.end|.<<outpu|
|00000f80| 74 20 61 20 70 61 67 65 | 20 6f 66 20 61 6e 73 77 |t a page| of answ|
|00000f90| 65 72 73 3e 3e 3d 0d 62 | 65 67 69 6e 20 77 72 69 |ers>>=.b|egin wri|
|00000fa0| 74 65 28 27 54 68 65 20 | 46 69 72 73 74 20 27 29 |te('The |First ')|
|00000fb0| 3b 0d 77 72 69 74 65 28 | 6d 3a 31 29 3b 0d 77 72 |;.write(|m:1);.wr|
|00000fc0| 69 74 65 28 27 20 50 72 | 69 6d 65 20 4e 75 6d 62 |ite(' Pr|ime Numb|
|00000fd0| 65 72 73 20 2d 2d 2d 20 | 50 61 67 65 20 27 29 3b |ers --- |Page ');|
|00000fe0| 0d 77 72 69 74 65 28 70 | 61 67 65 5f 6e 75 6d 62 |.write(p|age_numb|
|00000ff0| 65 72 3a 31 29 3b 20 77 | 72 69 74 65 5f 6c 6e 3b |er:1); w|rite_ln;|
|00001000| 20 77 72 69 74 65 5f 6c | 6e 3b 0d 20 20 7b 20 74 | write_l|n;.  { t|
|00001010| 68 65 72 65 27 73 20 61 | 20 62 6c 61 6e 6b 20 6c |here's a| blank l|
|00001020| 69 6e 65 20 61 66 74 65 | 72 20 74 68 65 20 68 65 |ine afte|r the he|
|00001030| 61 64 69 6e 67 20 7d 0d | 66 6f 72 20 72 6f 77 5f |ading }.|for row_|
|00001040| 6f 66 66 73 65 74 20 3a | 3d 20 70 61 67 65 73 5f |offset :|= pages_|
|00001050| 6f 66 66 73 65 74 20 74 | 6f 20 70 61 67 65 5f 6f |offset t|o page_o|
|00001060| 66 66 73 65 74 20 2b 20 | 72 72 20 2d 20 31 20 0d |ffset + |rr - 1 .|
|00001070| 20 20 20 20 20 20 64 6f | 20 3c 3c 6f 75 74 70 75 |      do| <<outpu|
|00001080| 74 20 61 20 6c 69 6e 65 | 20 6f 66 20 61 6e 73 77 |t a line| of answ|
|00001090| 65 72 73 3e 3e 3b 0d 70 | 61 67 65 3b 0d 65 6e 64 |ers>>;.p|age;.end|
|000010a0| 0d 3c 3c 6f 75 74 70 75 | 74 20 61 20 6c 69 6e 65 |.<<outpu|t a line|
|000010b0| 20 6f 66 20 61 6e 73 77 | 65 72 73 3e 3e 3d 0d 62 | of answ|ers>>=.b|
|000010c0| 65 67 69 6e 20 66 6f 72 | 20 63 20 3a 3d 20 30 20 |egin for| c := 0 |
|000010d0| 74 6f 20 63 63 20 2d 20 | 31 20 64 6f 0d 20 20 69 |to cc - |1 do.  i|
|000010e0| 66 20 66 6f 72 5f 6f 66 | 66 73 65 74 20 2b 20 63 |f for_of|fset + c|
|000010f0| 20 2a 20 72 72 20 3c 3d | 20 6d 20 74 68 65 6e 0d | * rr <=| m then.|
|00001100| 20 20 20 20 77 72 69 74 | 65 28 70 5b 72 6f 77 5f |    writ|e(p[row_|
|00001110| 6f 66 66 73 65 74 20 2b | 20 63 20 2a 20 72 72 5d |offset +| c * rr]|
|00001120| 29 3b 0d 77 72 69 74 65 | 6c 6e 3b 0d 65 6e 64 0d |);.write|ln;.end.|
|00001130| 40 0d 5c 73 65 63 74 69 | 6f 6e 7b 47 65 6e 65 72 |@.\secti|on{Gener|
|00001140| 61 74 69 6e 67 20 74 68 | 65 20 70 72 69 6d 65 73 |ating th|e primes|
|00001150| 7d 0d 3c 3c 66 69 6c 6c | 20 74 61 62 6c 65 20 5b |}.<<fill| table [|
|00001160| 5b 70 5d 5d 20 77 69 74 | 68 20 74 68 65 20 66 69 |[p]] wit|h the fi|
|00001170| 72 73 74 20 5b 5b 6d 5d | 5d 20 70 72 69 6d 65 20 |rst [[m]|] prime |
|00001180| 6e 75 6d 62 65 72 73 3e | 3e 3d 0d 3c 3c 69 6e 69 |numbers>|>=.<<ini|
|00001190| 74 69 61 6c 69 7a 65 20 | 74 68 65 20 64 61 74 61 |tialize |the data|
|000011a0| 20 73 74 72 75 63 74 75 | 72 65 73 3e 3e 0d 77 68 | structu|res>>.wh|
|000011b0| 69 6c 65 20 6b 20 3c 20 | 6d 20 64 6f 0d 20 20 62 |ile k < |m do.  b|
|000011c0| 65 67 69 6e 20 3c 3c 69 | 6e 63 72 65 61 73 65 20 |egin <<i|ncrease |
|000011d0| 5b 5b 6a 5d 5d 20 75 6e | 74 69 6c 20 69 74 20 69 |[[j]] un|til it i|
|000011e0| 73 20 74 68 65 20 6e 65 | 78 74 20 70 72 69 6d 65 |s the ne|xt prime|
|000011f0| 20 6e 75 6d 62 65 72 3e | 3e 0d 20 20 6b 20 3a 3d | number>|>.  k :=|
|00001200| 20 6b 20 2b 20 31 3b 20 | 70 5b 6b 5d 20 3a 3d 20 | k + 1; |p[k] := |
|00001210| 6a 3b 0d 20 20 65 6e 64 | 0d 3c 3c 76 61 72 69 61 |j;.  end|.<<varia|
|00001220| 62 6c 65 73 20 6f 66 20 | 74 68 65 20 70 72 6f 67 |bles of |the prog|
|00001230| 72 61 6d 3e 3e 3d 0d 6a | 3a 20 69 6e 74 65 67 65 |ram>>=.j|: intege|
|00001240| 72 3b 20 20 7b 20 61 6c | 6c 20 70 72 69 6d 65 73 |r;  { al|l primes|
|00001250| 20 3c 3d 20 6a 20 61 72 | 65 20 69 6e 20 74 61 62 | <= j ar|e in tab|
|00001260| 6c 65 20 70 20 7d 0d 6b | 3a 20 30 2e 2e 6d 3b 20 |le p }.k|: 0..m; |
|00001270| 20 20 20 20 7b 20 74 68 | 69 73 20 6d 61 6e 79 20 |    { th|is many |
|00001280| 70 72 69 6d 65 73 20 61 | 72 65 20 69 6e 20 74 61 |primes a|re in ta|
|00001290| 62 6c 65 20 70 20 7d 0d | 3c 3c 69 6e 63 72 65 61 |ble p }.|<<increa|
|000012a0| 73 65 20 5b 5b 6a 5d 5d | 20 75 6e 74 69 6c 20 69 |se [[j]]| until i|
|000012b0| 74 20 69 73 20 74 68 65 | 20 6e 65 78 74 20 70 72 |t is the| next pr|
|000012c0| 69 6d 65 20 6e 75 6d 62 | 65 72 3e 3e 3d 0d 72 65 |ime numb|er>>=.re|
|000012d0| 70 65 61 74 20 6a 20 3a | 3d 20 6a 20 2b 20 32 3b |peat j :|= j + 2;|
|000012e0| 0d 20 20 3c 3c 75 70 64 | 61 74 65 20 76 61 72 69 |.  <<upd|ate vari|
|000012f0| 61 62 6c 65 73 20 74 68 | 61 74 20 64 65 70 65 6e |ables th|at depen|
|00001300| 64 20 6f 6e 20 5b 5b 6a | 5d 5d 3e 3e 3b 0d 20 20 |d on [[j|]]>>;.  |
|00001310| 3c 3c 67 69 76 65 20 74 | 6f 20 5b 5b 6a 5f 70 72 |<<give t|o [[j_pr|
|00001320| 69 6d 65 5d 5d 20 74 68 | 65 20 6d 65 61 6e 69 6e |ime]] th|e meanin|
|00001330| 67 3a 20 5b 5b 6a 5d 5d | 20 69 73 20 61 20 70 72 |g: [[j]]| is a pr|
|00001340| 69 6d 65 20 6e 75 6d 62 | 65 72 3e 3e 0d 75 6e 74 |ime numb|er>>.unt|
|00001350| 69 6c 20 6a 5f 70 72 69 | 6d 65 0d 3c 3c 76 61 72 |il j_pri|me.<<var|
|00001360| 69 61 62 6c 65 73 20 6f | 66 20 74 68 65 20 70 72 |iables o|f the pr|
|00001370| 6f 67 72 61 6d 3e 3e 3d | 0d 6a 5f 70 72 69 6d 65 |ogram>>=|.j_prime|
|00001380| 3a 20 62 6f 6f 6c 65 61 | 6e 3b 0d 40 20 25 64 65 |: boolea|n;.@ %de|
|00001390| 66 20 6a 5f 70 72 69 6d | 65 0d 3c 3c 69 6e 69 74 |f j_prim|e.<<init|
|000013a0| 69 61 6c 69 7a 65 20 74 | 68 65 20 64 61 74 61 20 |ialize t|he data |
|000013b0| 73 74 72 75 63 74 75 72 | 65 73 3e 3e 3d 0d 6a 20 |structur|es>>=.j |
|000013c0| 3a 3d 20 31 3b 20 6b 20 | 3a 3d 20 31 3b 20 70 5b |:= 1; k |:= 1; p[|
|000013d0| 31 5d 20 3a 3d 20 32 3b | 0d 3c 3c 76 61 72 69 61 |1] := 2;|.<<varia|
|000013e0| 62 6c 65 73 20 6f 66 20 | 74 68 65 20 70 72 6f 67 |bles of |the prog|
|000013f0| 72 61 6d 3e 3e 3d 0d 6f | 72 64 3a 20 32 2e 2e 6f |ram>>=.o|rd: 2..o|
|00001400| 72 64 5f 6d 61 78 3b 0d | 20 20 7b 20 74 68 65 20 |rd_max;.|  { the |
|00001410| 73 6d 61 6c 6c 65 73 74 | 20 69 6e 64 65 78 20 3e |smallest| index >|
|00001420| 3d 20 32 20 73 75 63 68 | 20 74 68 61 74 20 70 5f |= 2 such| that p_|
|00001430| 6f 72 64 20 73 71 75 61 | 72 65 64 20 3e 20 6a 20 |ord squa|red > j |
|00001440| 7d 0d 73 71 75 61 72 65 | 3a 20 69 6e 74 65 67 65 |}.square|: intege|
|00001450| 72 3b 0d 20 20 7b 20 73 | 71 75 61 72 65 20 3d 20 |r;.  { s|quare = |
|00001460| 70 5f 6f 72 64 20 73 71 | 75 61 72 65 64 20 7d 0d |p_ord sq|uared }.|
|00001470| 40 20 25 64 65 66 20 6f | 72 64 20 73 71 75 61 72 |@ %def o|rd squar|
|00001480| 65 0d 3c 3c 69 6e 69 74 | 69 61 6c 69 7a 65 20 74 |e.<<init|ialize t|
|00001490| 68 65 20 64 61 74 61 20 | 73 74 72 75 63 74 75 72 |he data |structur|
|000014a0| 65 73 3e 3e 3d 0d 6f 72 | 64 20 3a 3d 20 32 3b 20 |es>>=.or|d := 2; |
|000014b0| 73 71 75 61 72 65 20 3a | 3d 20 39 3b 0d 3c 3c 6f |square :|= 9;.<<o|
|000014c0| 74 68 65 72 20 63 6f 6e | 73 74 61 6e 74 73 20 6f |ther con|stants o|
|000014d0| 66 20 74 68 65 20 70 72 | 6f 67 72 61 6d 3e 3e 3d |f the pr|ogram>>=|
|000014e0| 0d 6f 72 64 5f 6d 61 78 | 20 3d 20 33 30 3b 20 20 |.ord_max| = 30;  |
|000014f0| 7b 20 70 5f 6f 72 64 5f | 6d 61 78 20 73 71 75 61 |{ p_ord_|max squa|
|00001500| 72 65 64 20 6d 75 73 74 | 20 65 78 63 65 65 64 20 |red must| exceed |
|00001510| 70 5f 6d 20 7d 0d 3c 3c | 75 70 64 61 74 65 20 76 |p_m }.<<|update v|
|00001520| 61 72 69 61 62 6c 65 73 | 20 74 68 61 74 20 64 65 |ariables| that de|
|00001530| 70 65 6e 64 20 6f 6e 20 | 5b 5b 6a 5d 5d 3e 3e 3d |pend on |[[j]]>>=|
|00001540| 0d 69 66 20 6a 20 3d 20 | 73 71 75 61 72 65 20 74 |.if j = |square t|
|00001550| 68 65 6e 0d 20 20 62 65 | 67 69 6e 20 6f 72 64 20 |hen.  be|gin ord |
|00001560| 3a 3d 20 6f 72 64 20 2b | 20 31 3b 0d 20 20 3c 3c |:= ord +| 1;.  <<|
|00001570| 75 70 64 61 74 65 20 76 | 61 72 69 61 62 6c 65 73 |update v|ariables|
|00001580| 20 74 68 61 74 20 64 65 | 70 65 6e 64 20 6f 6e 20 | that de|pend on |
|00001590| 5b 5b 6f 72 64 5d 5d 3e | 3e 0d 20 20 65 6e 64 0d |[[ord]]>|>.  end.|
|000015a0| 3c 3c 75 70 64 61 74 65 | 20 76 61 72 69 61 62 6c |<<update| variabl|
|000015b0| 65 73 20 74 68 61 74 20 | 64 65 70 65 6e 64 20 6f |es that |depend o|
|000015c0| 6e 20 5b 5b 6f 72 64 5d | 5d 3e 3e 3d 0d 73 71 75 |n [[ord]|]>>=.squ|
|000015d0| 61 72 65 20 3a 3d 20 70 | 5b 6f 72 64 5d 20 2a 20 |are := p|[ord] * |
|000015e0| 70 5b 6f 72 64 5d 3b 20 | 20 7b 20 61 74 20 74 68 |p[ord]; | { at th|
|000015f0| 69 73 20 70 6f 69 6e 74 | 20 6f 72 64 20 3c 3d 20 |is point| ord <= |
|00001600| 6b 20 7d 0d 40 0d 5c 73 | 65 63 74 69 6f 6e 7b 54 |k }.@.\s|ection{T|
|00001610| 68 65 20 69 6e 6e 65 72 | 20 6c 6f 6f 70 7d 0d 3c |he inner| loop}.<|
|00001620| 3c 67 69 76 65 20 74 6f | 20 5b 5b 6a 5f 70 72 69 |<give to| [[j_pri|
|00001630| 6d 65 5d 5d 20 74 68 65 | 20 6d 65 61 6e 69 6e 67 |me]] the| meaning|
|00001640| 3a 20 5b 5b 6a 5d 5d 20 | 69 73 20 61 20 70 72 69 |: [[j]] |is a pri|
|00001650| 6d 65 20 6e 75 6d 62 65 | 72 3e 3e 3d 0d 6e 20 3a |me numbe|r>>=.n :|
|00001660| 3d 20 32 3b 20 6a 5f 70 | 72 69 6d 65 20 3a 3d 20 |= 2; j_p|rime := |
|00001670| 74 72 75 65 3b 0d 77 68 | 69 6c 65 20 28 6e 20 3c |true;.wh|ile (n <|
|00001680| 20 6f 72 64 29 20 61 6e | 64 20 6a 5f 70 72 69 6d | ord) an|d j_prim|
|00001690| 65 20 64 6f 0d 20 20 62 | 65 67 69 6e 20 3c 3c 69 |e do.  b|egin <<i|
|000016a0| 66 20 5b 5b 70 5b 6e 5d | 5d 5d 20 69 73 20 61 20 |f [[p[n]|]] is a |
|000016b0| 66 61 63 74 6f 72 20 6f | 66 20 5b 5b 6a 5d 5d 2c |factor o|f [[j]],|
|000016c0| 20 73 65 74 20 5b 5b 6a | 5f 70 72 69 6d 65 20 3a | set [[j|_prime :|
|000016d0| 3d 20 66 61 6c 73 65 5d | 5d 3e 3e 3b 0d 20 20 6e |= false]|]>>;.  n|
|000016e0| 20 3a 3d 20 6e 20 2b 20 | 31 3b 0d 20 20 65 6e 64 | := n + |1;.  end|
|000016f0| 0d 3c 3c 76 61 72 69 61 | 62 6c 65 73 20 6f 66 20 |.<<varia|bles of |
|00001700| 74 68 65 20 70 72 6f 67 | 72 61 6d 3e 3e 3d 0d 6e |the prog|ram>>=.n|
|00001710| 3a 20 32 2e 2e 6f 72 64 | 5f 6d 61 78 3b 20 7b 20 |: 2..ord|_max; { |
|00001720| 72 75 6e 73 20 66 72 6f | 6d 20 32 20 74 6f 20 6f |runs fro|m 2 to o|
|00001730| 72 64 20 77 68 65 6e 20 | 74 65 73 74 69 6e 67 20 |rd when |testing |
|00001740| 64 69 76 69 73 69 62 69 | 6c 69 74 79 20 7d 0d 3c |divisibi|lity }.<|
|00001750| 3c 76 61 72 69 61 62 6c | 65 73 20 6f 66 20 74 68 |<variabl|es of th|
|00001760| 65 20 70 72 6f 67 72 61 | 6d 3e 3e 3d 0d 6d 75 6c |e progra|m>>=.mul|
|00001770| 74 3a 20 61 72 72 61 79 | 20 5b 32 2e 2e 6f 72 64 |t: array| [2..ord|
|00001780| 5f 6d 61 78 5d 20 6f 66 | 20 69 6e 74 65 67 65 72 |_max] of| integer|
|00001790| 3b 0d 20 20 7b 20 72 75 | 6e 73 20 74 68 72 6f 75 |;.  { ru|ns throu|
|000017a0| 67 68 20 6d 75 6c 74 69 | 70 6c 65 73 20 6f 66 20 |gh multi|ples of |
|000017b0| 70 72 69 6d 65 73 20 7d | 0d 40 20 25 64 65 66 20 |primes }|.@ %def |
|000017c0| 6d 75 6c 74 0d 3c 3c 75 | 70 64 61 74 65 20 76 61 |mult.<<u|pdate va|
|000017d0| 72 69 61 62 6c 65 73 20 | 74 68 61 74 20 64 65 70 |riables |that dep|
|000017e0| 65 6e 64 20 6f 6e 20 5b | 5b 6f 72 64 5d 5d 3e 3e |end on [|[ord]]>>|
|000017f0| 3d 0d 6d 75 6c 74 5b 6f | 72 64 2d 31 5d 20 3a 3d |=.mult[o|rd-1] :=|
|00001800| 20 6a 3b 0d 3c 3c 69 66 | 20 5b 5b 70 5b 6e 5d 5d | j;.<<if| [[p[n]]|
|00001810| 5d 20 69 73 20 61 20 66 | 61 63 74 6f 72 20 6f 66 |] is a f|actor of|
|00001820| 20 5b 5b 6a 5d 5d 2c 20 | 73 65 74 20 5b 5b 6a 5f | [[j]], |set [[j_|
|00001830| 70 72 69 6d 65 20 3a 3d | 20 66 61 6c 73 65 5d 5d |prime :=| false]]|
|00001840| 3e 3e 3d 0d 77 68 69 6c | 65 20 6d 75 6c 74 5b 6e |>>=.whil|e mult[n|
|00001850| 5d 20 3c 20 6a 20 64 6f | 0d 20 20 6d 75 6c 74 5b |] < j do|.  mult[|
|00001860| 6e 5d 20 3a 3d 20 6d 75 | 6c 74 5b 6e 5d 20 2b 20 |n] := mu|lt[n] + |
|00001870| 70 5b 6e 5d 20 2b 20 70 | 5b 6e 5d 3b 0d 69 66 20 |p[n] + p|[n];.if |
|00001880| 6d 75 6c 74 5b 6e 5d 20 | 3d 20 6a 20 74 68 65 6e |mult[n] |= j then|
|00001890| 20 6a 5f 70 72 69 6d 65 | 20 3a 3d 20 66 61 6c 73 | j_prime| := fals|
|000018a0| 65 3b 0d 40 0d 5c 73 65 | 63 74 69 6f 6e 7b 49 6e |e;.@.\se|ction{In|
|000018b0| 64 65 78 7d 0d 5c 73 75 | 62 73 65 63 74 69 6f 6e |dex}.\su|bsection|
|000018c0| 7b 43 68 75 6e 6b 73 7d | 0d 5c 6e 6f 77 65 62 63 |{Chunks}|.\nowebc|
|000018d0| 68 75 6e 6b 73 0d 5c 73 | 75 62 73 65 63 74 69 6f |hunks.\s|ubsectio|
|000018e0| 6e 7b 49 64 65 6e 74 69 | 66 69 65 72 73 7d 0d 5c |n{Identi|fiers}.\|
|000018f0| 6e 6f 77 65 62 69 6e 64 | 65 78 0d 0d 5c 62 69 62 |nowebind|ex..\bib|
|00001900| 6c 69 6f 67 72 61 70 68 | 79 73 74 79 6c 65 7b 75 |liograph|ystyle{u|
|00001910| 6e 73 72 74 7d 0d 5c 62 | 69 62 6c 69 6f 67 72 61 |nsrt}.\b|ibliogra|
|00001920| 70 68 79 7b 77 65 62 2c | 63 73 2c 72 61 6d 73 65 |phy{web,|cs,ramse|
|00001930| 79 7d 0d                |                         |y}.     |        |
+--------+-------------------------+-------------------------+--------+--------+